package com.dmall.chapter03.section04;

import java.util.*;

/**
 * 先排序，然后使用双指针
 * 时间复杂度：排序的时间复杂度是：O(nlogn)，双指针的时间复杂度是：O(n)，所以总体的时间复杂度是：O(nlogn)
 * 空间复杂度：O(n)，由于使用了一个map存数据，所以空间复杂度是：O(n)
 * @author xiao1.wang
 * @date 2020-12-01 22:38:34
 */
public class Leetcode1V2 {

    public int[] twoSum(int[] nums, int target) {
        List<Item> items = sort(nums);
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            if (target == items.get(start).value + items.get(end).value) {
                return new int[]{items.get(start).index, items.get(end).index};
            } else if (target > items.get(start).value + items.get(end).value) {
                start++;
            } else {
                end--;
            }
        }
        return null;
    }

    class Item {
        int value;
        int index;
    }

    private List<Item> sort(int[] nums) {
        List<Item> items = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            Item item = new Item();
            item.value = nums[i];
            item.index = i;
            items.add(item);
        }
        items.sort(Comparator.comparingInt(o -> o.value));
        return items;
    }

    /*public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(nums.length * 100 / 75 + 1);
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        Arrays.sort(nums);

        int left = 0, right = nums.length - 1;
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                return new int[] {map.get(nums[left]), map.get(nums[right])};
            } else if (nums[left] + nums[right] < target) {
                left++;
            } else {
                right --;
            }
        }
        return null;
    }*/

    public static void main(String[] args) {
        int[] nums = {3, 3};
        Leetcode1V2 leetcode1 = new Leetcode1V2();
        int[] res = leetcode1.twoSum(nums, 6);
        System.out.println(Arrays.toString(res));
    }
}
